CODE 9. Binary Tree Maximum Path Sum

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/16/2013-09-16-CODE 9 Binary Tree Maximum Path Sum/

访问原文「CODE 9. Binary Tree Maximum Path Sum」

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3

Return 6.

int max;

public int maxPathSum(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return 0;
	}
	if (null == root.left && null == root.right) {
		return root.val;
	}
	this.max = Integer.MIN_VALUE;
	calcMax(root);
	return this.max;
}

private int calcMax(TreeNode root) {
	if (null == root) {
		return 0;
	}
	if (null == root.left && null == root.right) {
		this.max = this.max > root.val ? this.max : root.val;
		return root.val;
	}
	int left = 0;
	int right = 0;
	if (null != root.left) {
		left = calcMax(root.left);
	}
	if (null != root.right) {
		right = calcMax(root.right);
	}
	int tmpMax = left + right + root.val > root.val ? left + right
			+ root.val : root.val;
	int tmpLRMax = right + root.val > left + root.val ? right + root.val
			: left + root.val;
	tmpMax = tmpMax > tmpLRMax ? tmpMax : tmpLRMax;
	this.max = this.max > tmpMax ? this.max : tmpMax;
	return tmpLRMax > root.val ? tmpLRMax : root.val;
}